//
// Created by edward on 22-11-17.
// 使用Miller Rabin算法单机求解1e8以内的所有素数
// 输出执行时间 素数总数 素数总和
//      从小到大输出最大的10个素数
//

#include "utils.h"
#include "miller_rabin.h"
#include <vector>
#include <fstream>
#include <cstring>
#include <thread>

using namespace std;

using ll = long long;

constexpr int kMax = 1e8;
int prime[kMax];
ll sum = 0, t;
int cnt = 0, lastCnt;

void output(edward::Timer& timer, const string& path) {
    ofstream os(path);
    //输出
    edward::print2file(os, "execution time:", timer.count(), "s");
    edward::print2file(os, "total number of primes found:", cnt);
    edward::print2file(os, "sum of all primes found:", sum);
    for (int i = lastCnt - 10, idx = 1; i < lastCnt; ++i, ++idx) {
        edward::print2file(os, idx, ":", prime[i]);
    }
}

void cal_prime(int l, int r, int &cnt, ll &sum) {

    constexpr int kk = 5;

    //线性筛算法
    for (int i = l; i < r; ++i) {
        if (gfg::isPrime(i, kk)) {
            prime[cnt++] = i;
            sum += i;
        }
    }

}

void cal_prime_parallel() {
    edward::Timer timer;

    int l = 2, r = kMax;
    int threadNum = thread::hardware_concurrency(); //获取主机核数
    if (threadNum == 0) threadNum = 1;  //std::thread::hardware_concurrency()有可能返回0，正常情况下返回主机的核数8

    edward::print("parallel number:", threadNum);

    int block = (r - l) / threadNum;

    vector<thread> threads;
    vector<int> idxs(threadNum);
    vector<ll> sums(threadNum);

    int idx = l;
    for (int i = 0; i < threadNum - 1; ++i) {
        idxs[i] = idx;
        threads.emplace_back(cal_prime, idx, idx + block, std::ref(idxs[i]), std::ref(sums[i]));
        idx += block;
    }
    idxs.back() = idx;
    //之所以把最后一个线程放在外面是为了处理 block不是整除的情况，这是并行算法处理并行处理区间的常用技巧
    threads.emplace_back(cal_prime, idx, r, std::ref(idxs.back()), std::ref(sums.back()));
    idx = l;
    for (int i = 0; i < threadNum; ++i) {
        threads[i].join();
        cnt += idxs[i] - idx;
        idx += block;
        sum += sums[i];
    }
    lastCnt = idxs.back();

    timer("time:");
    output(timer, "primes_number_v2.txt");
}

int main() {

    cal_prime_parallel();

    return 0;
}